package main.leetcode.clockin.May;

/**
 * 45.跳跃游戏II
 *
 * <p>给定一个非负整数数组，你最初位于数组的第一个位置。
 *
 * <p>数组中的每个元素代表你在该位置可以跳跃的最大长度。
 *
 * <p>你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 *
 * <p>示例: 输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。   从下标为 0 跳到下标为 1
 * 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
 *
 * <p>说明: 假设你总是可以到达数组的最后一个位置。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/jump-game-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day4 {
    private int res;

    public static void main(String[] args) {
        System.out.println(new day4().jump(new int[] {2, 3, 1, 1, 4}));
        System.out.println(new day4().jump(new int[] {2, 1}));
    }

    //    public int jump(int[] nums) {
    //        res = Integer.MAX_VALUE;
    //        jump(nums, 0, 0);
    //        return res;
    //    }

    private void jump(int[] nums, int i, int cur) {
        if (i == nums.length - 1) {
            res = Math.min(res, cur);
            return;
        }
        ++cur;
        for (int j = 1; j <= nums[i]; ++j) {
            if (j >= nums.length - i) {
                break;
            }
            jump(nums, i + j, cur);
        }
    }

    public int jump(int[] nums) {
        int res = 0;
        int cur = 0;
        // 记录能到达的最远位置
        int maxPos = 0;
        // 记录边界
        int end = 0;
        while (end < nums.length - 1) {
            maxPos = Math.max(maxPos, cur + nums[cur]);
            // 到达边界
            if (cur == end) {
                // 更新边界为最远能到达位置
                end = maxPos;
                // 增加跳跃次数
                ++res;
            }
            ++cur;
        }
        return res;
    }
}
